package com.leetcode.algorithm.y22.m08.w2;

import java.util.ArrayList;
import java.util.List;

/**
 * 78. 子集
 * 
 * https://leetcode.cn/problems/subsets/
 * 
 * @author jie.deng
 *
 */
class Question0078Solution01 {

	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> list = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		subsets(nums, list, 0, path);
		return list;
	}

	private void subsets(int[] nums, List<List<Integer>> list, int idx, List<Integer> path) {
		int len = nums.length;
		if (idx == len) {
			list.add(new ArrayList<>(path));
			return;
		}
		// 包含当前元素
		path.add(nums[idx]);
		subsets(nums, list, idx + 1, path);
		path.remove(path.size() - 1);

		// 不包含当前元素
		subsets(nums, list, idx + 1, path);

	}

}